package tencent_practice;

import structure.ListNode;

/**
 * 旋转链表
 * 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
 */
public class Tencent_61_rotateRight {
    /**
     * 自己做，错了
     * @param head
     * @param k
     * @return
     */
    public ListNode rotateRight(ListNode head, int k) {
//        ListNode node = new ListNode();
//        node = head;
//        ListNode fast = node;
//        ListNode low = node;
//        int index = 0;
//        int n = 0;
//        for(ListNode p = head; p != null ; p = p.next){
//            n++;
//        }
//        while (node.next != null && index != k % n) {
//            fast = node.next;
//            index++;
//        }
//        while (fast.next.next != null && fast.next != null) {
//            fast = fast.next;
//            low = low.next;
//        }
//        ListNode res = new ListNode();
//        res.next = low.next;
//        low.next = null;
//        res.next.next.next = node;
//        return res.next;

        if(head == null|| k == 0)  return head;
        int n = 0;			   //链表的长度
        ListNode tail = null;  //尾节点
        for(ListNode p = head; p != null ; p = p.next){
            tail = p;
            n++;
        }
        k %= n;
        ListNode p = head;
        for(int i = 0; i < n - k - 1; i++)  p = p.next;   //找到链表的第n-k个节点
        tail.next = head;
        head = p.next;
        p.next = null;
        return head;  //返回新的头节点

    }
}
